#ifndef LISTA_H
#define LISTA_H

template<class T> struct ListaTetel
{
    T _data;
    ListaTetel* _prev;
    ListaTetel* _next;
    ListaTetel(ListaTetel* prev, ListaTetel* next):_prev(prev),_next(next){}
    ListaTetel(T data, ListaTetel* prev, ListaTetel* next):_data(data),_prev(prev),_next(next){}
};

template<class T> class Iterator
{
        ListaTetel<T>* _current;
    public:
        Iterator(){}
        Iterator(ListaTetel<T>* t)
        {
            _current = t;
        }
        Iterator(const Iterator<T>& rhs)
        {
           _current = rhs._current;
        }
        operator ListaTetel<T>*()
        {
            return _current;
        }
        Iterator& operator++()
        {
            _current = _current -> _next;
        }
        Iterator& operator--()
        {
            _current = _current -> _prev;
        }
        T& operator*()
        {
            return _current -> _data;
        }
        bool operator==(Iterator& rhs)
        {
            return (_current == rhs._current);
        }
        bool operator!=(const Iterator<T>& rhs)
        {
            return (_current != rhs._current);
        }
};

template<class T> class Lista
{
        ListaTetel<T>* _head;
        ListaTetel<T>* _tail;
        int _size;
    public:
        enum Kivetelek{LIST_IS_EMPTY};
        Lista()
        {
            _head = new ListaTetel<T>(NULL, NULL);
            _tail = new ListaTetel<T>(NULL, NULL);
            _size = 0;
            _head -> _next = _tail;
            _tail -> _prev = _head;
        }
        ~Lista()
        {
            while (_head != _tail)
            {
                ListaTetel<T>* tmp = _head;
                _head = _head -> _next;
                delete tmp;
            }
            delete _tail;
        }
        Lista(Lista& rhs)
        {
            if (this != &rhs)
            {
                if (rhs.Begin() == NULL)
                {
                    _head = new ListaTetel<T>(NULL, NULL);
                    _tail = new ListaTetel<T>(NULL, NULL);
                    _size = 0;
                    _head -> _next = _tail;
                    _tail -> _prev = _head;
                }
                else
                {
                    Iterator<T> it(rhs.Begin());
                    _head = new ListaTetel<T>(NULL, NULL);
                    _head->_next = new ListaTetel<T>(*it, _head, NULL);
                    ListaTetel<T>* _current = _head->_next;
                    ++it;
                    while (it != rhs.End())
                    {
                        _current -> _next = new ListaTetel<T>(*it, _current, NULL);
                        _current = _current -> _next;
                        ++it;
                    }
                    _tail  = new ListaTetel<T>(_current, NULL);
                    _current -> _next = _tail;
                    _size = rhs.Size();
                }
            }
        }
        Lista(const Lista& rhs)
        {
            if (this != &rhs)
            {
                if (rhs.Begin() == NULL)
                {
                    _head = new ListaTetel<T>(NULL, NULL);
                    _tail = new ListaTetel<T>(NULL, NULL);
                    _size = 0;
                    _head -> _next = _tail;
                    _tail -> _prev = _head;
                }
                else
                {
                    Iterator<T> it(rhs.Begin());
                    _head = new ListaTetel<T>(NULL, NULL);
                    _head->_next = new ListaTetel<T>(*it, _head, NULL);
                    ListaTetel<T>* _current = _head->_next;
                    ++it;
                    while (it != rhs.End())
                    {
                        _current -> _next = new ListaTetel<T>(*it, _current, NULL);
                        _current = _current -> _next;
                        ++it;
                    }
                    _tail  = new ListaTetel<T>(_current, NULL);
                    _current -> _next = _tail;
                    _size = rhs.Size();
                }
            }
        }
        Lista& operator=(Lista& rhs)
        {
            if (this != &rhs)
            {
                if (rhs.Begin() == NULL)
                {
                    _head = new ListaTetel<T>(NULL, NULL);
                    _tail = new ListaTetel<T>(NULL, NULL);
                    _size = 0;
                    _head -> _next = _tail;
                    _tail -> _prev = _head;
                }
                else
                {
                    Iterator<T> it(rhs.Begin());
                    _head = new ListaTetel<T>(NULL, NULL);
                    _head->_next = new ListaTetel<T>(*it, _head, NULL);
                    ListaTetel<T>* _current = _head->_next;
                    ++it;
                    while (it != rhs.End())
                    {
                        _current -> _next = new ListaTetel<T>(*it, _current, NULL);
                        _current = _current -> _next;
                        ++it;
                    }
                    _tail  = new ListaTetel<T>(_current, NULL);
                    _current -> _next = _tail;
                    _size = rhs.Size();
                }
            }
            return (*this);
        }
        Lista& operator=(const Lista& rhs)
        {
            if (this != &rhs)
            {
                if (rhs.Begin() == NULL)
                {
                    _head = new ListaTetel<T>(NULL, NULL);
                    _tail = new ListaTetel<T>(NULL, NULL);
                    _size = 0;
                    _head -> _next = _tail;
                    _tail -> _prev = _head;
                }
                else
                {
                    Iterator<T> it(rhs.Begin());
                    _head = new ListaTetel<T>(NULL, NULL);
                    _head->_next = new ListaTetel<T>(*it, _head, NULL);
                    ListaTetel<T>* _current = _head->_next;
                    ++it;
                    while (it != rhs.End())
                    {
                        _current -> _next = new ListaTetel<T>(*it, _current, NULL);
                        _current = _current -> _next;
                        ++it;
                    }
                    _tail  = new ListaTetel<T>(_current, NULL);
                    _current -> _next = _tail;
                    _size = rhs.Size();
                }
            }
            return (*this);
        }
        Iterator<T> Begin() const
        {
            return Iterator<T>(_head->_next);
        }
        Iterator<T> End() const
        {
            return Iterator<T>(_tail);
        }
        Iterator<T> RBegin() const
        {
            return Iterator<T>(_tail->_prev);
        }
        Iterator<T> REnd() const
        {
            return Iterator<T>(_head);
        }
        void Insert (Iterator<T>& it, T data)
        {
            ListaTetel<T>* tmp = new ListaTetel<T>(data, (*it)._prev, (*it));
            tmp->_prev->_next = tmp;
            (*it)._prev = tmp;
            _size++;
        }
        void InsertFirst(T data)
        {
            ListaTetel<T>* tmp = new ListaTetel<T>(data, _head, _head->_next);
            _head -> _next = tmp;
            tmp -> _next -> _prev = tmp;
            _size++;
        }
        void InsertLast(T data)
        {
            ListaTetel<T>* tmp = new ListaTetel<T>(data, _tail->_prev, _tail);
            _tail -> _prev = tmp;
            tmp -> _prev -> _next = tmp;
            _size++;
        }
        T Remove (Iterator<T>& it)
        {
            if (_size > 0)
            {
                ListaTetel<T>* tmp = it;
                tmp -> _prev -> _next = tmp -> _next;
                tmp -> _next -> _prev = tmp -> _prev;
                T r = tmp -> _data;
                delete tmp;
                _size--;
                return r;
            }
            else
            {
                throw LIST_IS_EMPTY;
            }
        }
        T RemoveFirst()
        {
            if (_size > 0)
            {
                ListaTetel<T>* tmp = _head -> _next;
                _head -> _next = tmp -> _next;
                tmp -> _next -> _prev = _head;
                T r = tmp -> _data;
                delete tmp;
                _size--;
                return r;
            }
            else
            {
                throw LIST_IS_EMPTY;
            }
        }
        T RemoveLast()
        {
            if (_size > 0)
            {
                ListaTetel<T>* tmp = _tail -> _prev;
                _tail -> _prev = tmp -> _prev;
                tmp -> _prev -> _next = _tail;
                T r = tmp -> _data;
                delete tmp;
                _size--;
                return r;
            }
            else
            {
                throw LIST_IS_EMPTY;
            }
        }
        void Clear()
        {
            while (_head -> _next != _tail)
            {
                ListaTetel<T>* tmp = _head;
                _head = _head -> _next;
                delete tmp;
            }
            _size = 0;
        }
        int Size() const
        {
            return _size;
        }
        friend std::ostream& operator<<(std::ostream& os, const Lista& l)
        {
            for (Iterator<T> it = l.Begin(); it != l.End(); ++it)
            {
                os << (*it) << " ";
            }
            return os;
        }
};

#endif
